/*
 * solve.cpp - utilizes backtracking DFS to solve a Sudoku puzzle
 * Yet Another Sudoku Solver 
 * CSCE 411
 * by Michael Atkinson
 */

#include "common.h"

int check(vector<vector<char> > &puzzle, unsigned int r, unsigned int c);

int solve(vector<vector<char> > &puzzle, set<char> &trtable, unsigned int r, unsigned int c)
{
	for(set<char>::iterator iter = trtable.begin(); iter != trtable.end(); iter++)
	{
		if(puzzle[r][c] != '.')					// this cell is already filled
		{
			if(c < puzzle.size() - 1)			// not at the end of a row
				return solve(puzzle, trtable, r, c + 1);
			else								// at the end of a row
			{
				if(r < puzzle.size() - 1)		// not at the bottom of the puzzle
					return solve(puzzle, trtable, r + 1, 0);
				else
					return 1;					// found a solution
			}
		}
		else									// this cell is not already filled
		{
			puzzle[r][c] = *iter;				// value to check

			if(check(puzzle, r, c))				// the value preserves Sudoku rules
			{
				if(c < puzzle.size() - 1)		// not at the end of a row
				{
					if(!(solve(puzzle, trtable, r, c + 1)))	// dead end, clear cell and backtrack
						puzzle[r][c] = '.';
					else						// propagate the drop out of recursion up
						return 1;
				}
				else							// at the end of a row
				{
					if(r < puzzle.size() - 1)	// not at the bottom of the puzzle
					{
						if(!(solve(puzzle, trtable, r + 1, 0)))	// dead end, clear cell and backtrack
							puzzle[r][c] = '.';
						else
							return 1;			// propagate the drop out of recursion up
					}
					else
						return 1;				// found a solution, drop out of recursion
				}
			}
			else
				puzzle[r][c] = '.';				// the value does not preserve Sudoku rules
		}
	}

	return 0;									// no valid choices for this state, backtrack
}